# LeetCode 264、丑数II
# 一、题目描述
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1
输出：1
解释：1 通常被视为丑数。
提示：
1 <= n <= 1690
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 丑数II（LeetCode 264）（优先队列解法）：https://leetcode.cn/problems/ugly-number-ii/
class Solution {
public int nthUglyNumber(int n) {
// 对任意一个丑数来说，去和 2、3、5 分别相乘，可以得到 3 个丑数
// 那么对每一个丑数都去和 2 、3 、5 分别相乘，把那些结果进行排序即可
// 因此，2、3、5 就是我们需要处理的质因数
int[] factors = { 2 , 3 , 5 };
// 由于一些丑数和 2 、 3 、5 相乘会出现重复元素的情况
// 比如丑数 2 和 2 、 3 、5 相乘得到了 4、【6】、10
// 而丑数 3 和 2 、 3 、5 相乘得到了 【6】、9 、 15
// 其中 【6】重复了，所以需要采取去重操作
// 由于题目说明 n 最大为 1690，会导致丑数的范围超过了 int 范围，所以使用 long 来保存
Set<Long> seen = new HashSet<Long>();
// 使用优先队列来获取每次集合中最小的数字
// 由于题目说明 n 最大为 1690，会导致丑数的范围超过了 int 范围，所以使用 long 来保存
PriorityQueue<Long> pq = new PriorityQueue<Long>();
// 集合中第一个数字是 1
// 常量后面跟这种一般是指类型
// 1L 表示 1 是长整型，如果是 1f 表示是 float 型
seen.add(1L);
// 优先队列里面的元素来源于 seen
pq.offer(1L);
// 开始不断的迭代丑数的值，直到迭代了 n 次为止
// 第一个丑数是 1
int ugly = 1;
// 开始迭代
for (int i = 0; i < n; i++) {
// 下一个丑数来源于优先队列的队头元素
long curr = pq.poll();
// 本题需要返回 int 型，所以强转一下
ugly = (int) curr;
// 再将获取到的丑数和 2 、3 、5 分别相乘
for (int factor : factors) {
// 获取到新的丑数
long next = curr * factor;
// 经过去重操作后
if (seen.add(next)) {
// 把这个丑数加入到优先队列里面
// 优先队列里面会自动操作，使得最小的元素位于队头
pq.offer(next);
}
}
}
// 返回结果
return ugly;
}
}
# **2、**C++ 代码
class Solution {
public:
int nthUglyNumber(int n) {
// 对任意一个丑数来说，去和 2、3、5 分别相乘，可以得到 3 个丑数
// 那么对每一个丑数都去和 2 、3 、5 分别相乘，把那些结果进行排序即可
// 因此，2、3、5 就是我们需要处理的质因数
vector<int> factors = {2, 3, 5};
// 由于一些丑数和 2 、 3 、5 相乘会出现重复元素的情况
// 比如丑数 2 和 2 、 3 、5 相乘得到了 4、【6】、10
// 而丑数 3 和 2 、 3 、5 相乘得到了 【6】、9 、 15
// 其中 【6】重复了，所以需要采取去重操作
// 由于题目说明 n 最大为 1690，会导致丑数的范围超过了 int 范围，所以使用 long 来保存
unordered_set<long> seen;
// 使用优先队列来获取每次集合中最小的数字
// 由于题目说明 n 最大为 1690，会导致丑数的范围超过了 int 范围，所以使用 long 来保存
priority_queue<long, vector<long>, greater<long>> pq;
// 集合中第一个数字是 1
// 常量后面跟这种一般是指类型
// 1L 表示 1 是长整型，如果是 1f 表示是 float 型
seen.insert(1L);
// 优先队列里面的元素来源于 seen
pq.push(1L);
// 开始不断的迭代丑数的值，直到迭代了 n 次为止
// 第一个丑数是 1
int ugly = 1;
// 开始迭代
for (int i = 0; i < n; i++) {
// 下一个丑数来源于优先队列的队头元素
long curr = pq.top();
pq.pop();
// 本题需要返回 int 型，所以强转一下
ugly = (int) curr;
// 再将获取到的丑数和 2 、3 、5 分别相乘
for (int factor : factors) {
// 获取到新的丑数
long next = curr * factor;
// 经过去重操作后
if (!seen.count(next)) {
// 把这个丑数加入到优先队列里面
// 优先队列里面会自动操作，使得最小的元素位于队头
seen.insert(next);
pq.push(next);
}
}
}
// 返回结果
return ugly;
}
};
# 3、Python 代码
class Solution:
def nthUglyNumber(self, n: int) -> int:
# 对任意一个丑数来说，去和 2、3、5 分别相乘，可以得到 3 个丑数
# 那么对每一个丑数都去和 2 、3 、5 分别相乘，把那些结果进行排序即可
# 因此，2、3、5 就是我们需要处理的质因数
factors = [2, 3, 5]
# 由于一些丑数和 2 、 3 、5 相乘会出现重复元素的情况
# 比如丑数 2 和 2 、 3 、5 相乘得到了 4、【6】、10
# 而丑数 3 和 2 、 3 、5 相乘得到了 【6】、9 、 15
# 其中 【6】重复了，所以需要采取去重操作
# 由于题目说明 n 最大为 1690，会导致丑数的范围超过了 int 范围，所以使用 long 来保存
# 使用优先队列来获取每次集合中最小的数字
# 由于题目说明 n 最大为 1690，会导致丑数的范围超过了 int 范围，所以使用 long 来保存
# 集合中第一个数字是 1
# 常量后面跟这种一般是指类型
# 1L 表示 1 是长整型，如果是 1f 表示是 float 型
seen = {1}
# 优先队列里面的元素来源于 seen
pq = [1]
# 开始不断的迭代丑数的值，直到迭代了 n 次为止
# 第一个丑数是 1
# 开始迭代
for i in range(n - 1):
# 下一个丑数来源于优先队列的队头元素
curr = heapq.heappop(pq)
# 本题需要返回 int 型，所以强转一下
for factor in factors:
if (nxt := curr * factor) not in seen:
seen.add(nxt)
heapq.heappush(pq, nxt)
# 返回结果
return heapq.heappop(pq)